package Z.dailyExercise.May;

public class _19删除链表的倒数第N个结点 {

    /**
     *两次遍历
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {

        if (head.next == null){
            if (n == 1){
                return null;
            }

        }

        ListNode node = head;
        int len = 0;
        while (head!= null){
            len++;
            head = head.next;
        }

        if (len == n){
            return node.next;
        }

        int start = 0;
        ListNode newhead = node;
        while (start != len-n-1){
            node = node.next;
            start++;
        }
        node.next = node.next.next;


        return newhead;


    }

    /**
     * 快慢指针
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd1(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode fast = dummy;
        ListNode slow = dummy;

        while (n>0){
            fast = fast.next;
            n--;
        }
        while (fast.next != null){
            slow=  slow.next;
            fast = fast.next;
        }

        slow.next = slow.next.next;

        return dummy.next;
    }

}
